#include <iostream>
#include <utility>
#include <assert.h>
#include <queue>

using namespace std;

class BSTreeNode
{
public:
	int value;
	struct BSTreeNode * left;
	struct BSTreeNode * right;
	BSTreeNode(int v) : value(v), left(NULL), right(NULL) {
	}
};

class BSTree
{
	BSTreeNode * root;
public:
	BSTree(): root(NULL) {}

	BSTreeNode * getRoot() {
		return root;
	}
	
	void insert(int key) {
		BSTreeNode * n = new BSTreeNode(key);	
		insert(n);
	}

	void insert(BSTreeNode * node) {
		assert(node);
		if (root == NULL) {
			root = node;
			return;
		}

		BSTreeNode ** cur = &root;
		while(*cur != NULL) {
			if (node->value < (*cur)->value)
				cur = &((*cur)->left);
			else if (node->value > (*cur)->value)
				cur = &((*cur)->right);
			else
				break;
		}

		if(*cur == NULL)
			*cur = node;
	}
	
	static void print(BSTreeNode * root) {
		cout << root->value << " ";

		if (root->left)
			cout <<root->left->value<< " ";
		else
			cout << "NULL" << " ";
		if (root->right)
			cout << root->right->value << " ";
		else
			cout << "NULL" << " ";
		cout << endl;

		if (root->left)
			print(root->left);
		if (root->right)
			print(root->right);
	}

	void level_order_print() {
		if (root == NULL)
			return;

		queue<BSTreeNode *> st;
		st.push(root);
		int level_count = 1;	//the number of nodes at each level, initially, at level 0, there is only one node.

		while(level_count != 0) {
			int new_count = 0;
			for(int i = 0; i < level_count; i ++) {
				BSTreeNode * p = st.front();
				cout << p->value << " ";
				if (p->left) {
					st.push(p->left);
					new_count++;
				}
				if (p->right) {
					st.push(p->right);
					new_count++;
				}
				st.pop();
			}
			level_count = new_count;
		}
	}
};

int main()
{
	BSTree bst;
	for (int i = 0; i < 10; ++i)
		bst.insert(rand()%20);

	cout << "orig:" << endl;
	BSTree::print(bst.getRoot());
	
	bst.level_order_print();
	return 0;
}
